package Leetcode.sliding_window;

/**
 * @Author: kirito
 * @Date: 2024/9/27 16:08
 * @Description:
 * 给你一个由字符 'a'、'b'、'c' 组成的字符串 s 和一个非负整数 k 。每分钟，你可以选择取走 s 最左侧 还是 最右侧 的那个字符。
 *
 * 你必须取走每种字符 至少 k 个，返回需要的 最少 分钟数；如果无法取到，则返回 -1 。
 *
 * 示例 1：
 *
 * 输入：s = "aabaaaacaabc", k = 2
 * 输出：8
 * 解释：
 * 从 s 的左侧取三个字符，现在共取到两个字符 'a' 、一个字符 'b' 。
 * 从 s 的右侧取五个字符，现在共取到四个字符 'a' 、两个字符 'b' 和两个字符 'c' 。
 * 共需要 3 + 5 = 8 分钟。
 * 可以证明需要的最少分钟数是 8 。
 * 示例 2：
 *
 * 输入：s = "a", k = 1
 * 输出：-1
 * 解释：无法取到一个字符 'b' 或者 'c'，所以返回 -1 。
 */

public class 每种字符至少取K个 {
    public static void main(String[] args) {
        String s = "aabaaaacaabc";
        int k = 2;
        每种字符至少取K个 test = new 每种字符至少取K个();
        System.out.println(test.takeCharacters_1(s, k));
    }

    /**
     * 比如 s 中有 3 个 a，4 个 b，5 个 c，k=2，每种字母至少取走 2 个，等价于剩下的字母至多有 1 个 a，2 个 b 和 3 个 c。
     *
     * 由于只能从 s 最左侧和最右侧取走字母，所以剩下的字母是 s 的子串。
     *
     * 设 s 中的 a,b,c 的个数分别为 x,y,z，现在问题变成：
     *
     * 计算 s 的最长子串长度，该子串满足 a,b,c 的个数分别至多为 x−k,y−k,z−k。
     * 与其维护窗口内的字母个数，不如直接维护窗口外的字母个数，这也是我们取走的字母个数。
     *
     * 一开始，假设我们取走了所有的字母。或者说，初始窗口是空的，窗口外的字母个数就是 s 的每个字母的出现次数。
     * 右端点字母进入窗口后，该字母取走的个数减一。
     * 如果减一后，窗口外该字母的个数小于 k，说明子串太长了，或者取走的字母个数太少了，那么就不断右移左端点，把左端点字母移出窗口，相当于我们取走移出窗口的字母，直到该字母个数等于 k，退出内层循环。
     * 内层循环结束后，用窗口长度 right−left+1 更新子串长度的最大值。
     * 最后，原问题的答案为 n 减去子串长度的最大值。
     *
     * 特别地，如果 s 中某个字母的个数不足 k，那么无法满足题目要求，返回 −1。
     * 哇去，灵神的思维！~
     */
    public int takeCharacters_1(String S, int k) {
        char[] s = S.toCharArray();
        int[] cnt = new int[3];
        for (char c : s) {
            cnt[c - 'a']++; // 一开始，把所有字母都取走
        }
        if (cnt[0] < k || cnt[1] < k || cnt[2] < k) {
            return -1; // 字母个数不足 k
        }

        int mx = 0; // 子串最大长度
        int left = 0;
        for (int right = 0; right < s.length; right++) {
            int c = s[right] - 'a';
            cnt[c]--; // 移入窗口，相当于不取走 c
            while (cnt[c] < k) { // 窗口之外的 c 不足 k
                cnt[s[left] - 'a']++; // 移出窗口，相当于取走 s[left]
                left++;
            }
            mx = Math.max(mx, right - left + 1);
        }
        return s.length - mx;
    }

}
